package StudyCode.summary.mycollection;

import java.util.*;

/**
 * 版权所有 科技与人文(www.tah1986.com)
 */
public class ListAllCombinations {
	public static void main(String[] argv) {
		int n = 2;
		boolean zeroBased = true;
		System.out.println(listAllCombinations(n, zeroBased));
	}

	public static List<Set<Integer>> listAllCombinations(int n,
	                                                     boolean zeroBased) {
		List<Set<Integer>> allCombinations;

		allCombinations = new ArrayList<Set<Integer>>();
		for (int k = 0; k < n; k++) {
			allCombinations.addAll(listCombinationsFixed2(n, k, zeroBased));
		}

		return allCombinations;
	}

	public static List<Set<Integer>> listCombinationsFixed2(final int n,
	                                                        final int k, final boolean isZeroBased) {
		List<Set<Integer>> combinations = new ArrayList<Set<Integer>>();


		Integer[] combination = null;

		if (k == 0 || k == n) {
			combination = new Integer[n];
			for (int i = 0; i < n; i++) {
				combination[i] = i;
			}
		} else {
			combination = new Integer[k];
			for (int i = 0; i < k; i++) {
				combination[i] = i;
			}
		}

		if (isZeroBased) {
			combinations.add(new HashSet<Integer>(Arrays
					.asList(combination)));
		} else {
			Integer[] tempCombination = new Integer[combination.length];

			for (int i = 0; i < combination.length; i++) {
				tempCombination[i] = combination[i] + 1;
			}
			combinations.add(new HashSet<Integer>(Arrays
					.asList(tempCombination)));
		}

		while (nextCombination(combination, n, k)) {

			if (isZeroBased) {
				combinations.add(new HashSet<Integer>(Arrays
						.asList(combination)));
			} else {
				Integer[] tempCombination = new Integer[combination.length];

				for (int i = 0; i < combination.length; i++) {
					tempCombination[i] = combination[i] + 1;
				}
				combinations.add(new HashSet<Integer>(Arrays
						.asList(tempCombination)));
			}

		}

		return combinations;
	}

	private static boolean nextCombination(Integer comb[], int n, int k) {
		int i = k - 1;
		if (i == -1) {
			return false;
		}

		++comb[i];
		while ((i >= 0) && (comb[i] >= n - k + 1 + i)) {
			--i;
			if (i >= 0) {
				++comb[i];
			}
		}

		if (comb[0] > n - k)
			return false;

		for (i = i + 1; i < k; ++i)
			comb[i] = comb[i - 1] + 1;

		return true;
	}
}
